/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */


/**
 * 核心思想
 * 对于"PAYPALISHIRING"
 * 1层
 * 0  1  2  3  4 
 * 
 * 2层：间隔都为2（2+0），比如5与1
 * 0  2  4
 * 1  3  5
 * 
 * 3层为例：间隔都为4（3+1=3+ 3-2），比如3与7
 * 0     4     8
 * 1  3  5  7  9
 * 2     6     10
 * 
 * 4层为例：间隔都为6（4+2=4+ 4-2），比如5与1，且5为6-1
 * 0        6          12
 * 1     5  7      11  13
 * 2  4     8  10      14
 * 3        9          15
 * 
 * 根据上面的内容可推断：
 * 设要求为n行，则间隔/步长steer 为 (n + n-2)即2*n-2;
 * 设第i行，中间插入的mid=steer-i；
 * 
 * 
 * 第0行：首行，中间不用插入内容，则结果为：0，0+steer，0+steer+steer……
 * 第1行：中间需要插入一个内容(插入的用[]表示)，且从mid = [steer-1]开始，则结果为：1，mid，1+steer，mid+steer，1+steer + steer;
 * ……
 * 第n-1行：由于mid==i，也就是最后一行，中间也不用插入内容，则结果为：n-1，n-1+steer，n-1+steer+steer……
 * 
 * 
 * 综上：对于第i行，分为两种情况
 * 情况1：为首行或者最后一行，中间不用插入，则为i，i+steer，i+steer+steer……
 * 情况2：不是首行或者最后一行，中间要用插入，则为i，mid，i+steer，mid+steer，i+steer+steer……
 */

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        
        int i,mid;   // i 第几行的开始，mid表示中间插入的
        int steer;  // 步长
        string ans = "";
        steer = 2*numRows - 2;
        // cout << "steer: " << steer << endl;

        for (i = 0; i < numRows; i++) {
            mid=steer-i;
            // cout << "mid: " << mid << endl;
            if (mid == i || mid == steer) {
                for(int k=0; i + k < s.size(); k=k+steer) {
                    // cout << s[i+k] << endl;
                    // cout << i << ": " << k << endl;
                    ans.push_back(s[i+k]);
                }
            }
            else{
                for(int k=0; i + k < s.size(); k=k+steer) {
                    ans.push_back(s[i+k]);
                    if(mid + k < s.size()){  
                        ans.push_back(s[mid+k]);
                    }
                }
            }
            
        }
        return ans;
    }
};




int main(int argc, const char** argv) {
    Solution solu = Solution();
    string s = "PAYPALISHIRING";
    int numRows = 4;
    cout << s.size() << endl;
    cout << solu.convert(s, numRows) << endl;

    return 0;
}